/*
 * @lc app=leetcode.cn id=207 lang=golang
 *
 * [207] 课程表
 */

// @lc code=start
func canFinish(numCourses int, prerequisites [][]int) bool {
	edges := make([][]int, numCourses)
	visited := make([]bool, numCourses)
	valid := true
	var dfs func(u int)

	dfs = func(u int) {
		visited[u] = true

		for _, v := range edges[u] {
			if visited[u] {
				dfs(v)
				if !valid {
					return
				}
			} else {
				valid = false
				return
			}
		}
	}
	for _, v := range prerequisites {
		edges[v[1]] = append(edges[v[1]], v[0])
	}
	for i := 0; i < numCourses; i++ {
		if visited[i] {
			dfs(i)
		}
	}
	return valid

}

// @lc code=end

